In certain areas, like government, health care, human resources, and insurance, the daily processing of a variety of paper forms is a routine and important activity. The processing of a form often involves: the extraction of the information on the form supplied by the users; specific actions that are governed by the specific nature of the extracted information; and, possibly, the archiving of the extracted information and/or the form itself in a manner that facilitates subsequent use of the archival information. While all of these steps can, and often are, performed by a human, the processing of large number of forms on a timely basis by means of digital computing devices would be desirable.
One common step in the automation of forms handling is the digitization of one or more forms by means of an appropriate scanning device. The result of the scanning process is a set of information representing the digitized form. The set of information is normally a rectangular array of pixel elements—an “image”—of dimensions W and H where the “width”, W, is the number of pixels in each horizontal row of the array and the “height”, H, is the number of pixels in each vertical column of the pixel array. The columns may be identified, for purpose of discussing such a set of information, by an index, I, whose values can range from 0 to W-1; and the rows can be identified by an index J whose values range from 0 to H-1 where W, H, J and I are integer values. If a pixel array itself is labeled as IMG, then the value of a pixel in the column with index I and row with index J is labeled for discussion purposed as IMG[I,J]. The ordered pair [I,J] is sometimes called the “address” or “pixel location” of this pixel. This is illustrated in FIG. 1. FIG. 1 includes an exemplary pixel array 100 in which column 0 102, exemplary column I 104, column (W-1) 106, row 0 108, exemplary row J 110, row (H-1) 112, and exemplary pixel location [I,J] 114 are identified.
While the particular colors that are used on forms can vary from application to application, most forms have only two distinguishing color features, the background color and the foreground color. It is common practice to set the values of all pixels representing the background color to the number 1, as illustrated with background pixels 116 in FIG. 1, and all pixels representing the foreground color to the value 0, as illustrated with foreground pixels 118 in FIG. 1.
A not uncommon phenomenon in the scanning operation is that the digitized form is created at an angle to the original orientation of the form, as illustrated in image 300 of FIG. 3 (compare to image 200 of FIG. 2). Parts of the boundary of the original page may or may not be visible in the digitized form, as illustrated in FIG. 4. In either case, this perturbation of the form can present a serious impediment to high-level automated tasks such as form classification or optical character recognition.
Thus an automatic method of determining the rotation angle for the digitized form and digitally rotating the form to a straight orientation would be desirable. The operation of rotating the form by a known angle is straightforward and well-understood in the art. However, the problem of determining the correct rotation angle is much subtler and more complex, and there is a need for improved methods and apparatus to perform such operations.
In addition to determining the correct angle of rotation, it would be useful to be able to determine the boundaries of the original page within the image. Parts of this rectangle may even extend beyond the boundaries of the image matrix itself.
Thus there is a need for improved methods and apparatus that can be used to determine useful information for correcting rotation error in a scanned printed form, Examples of useful information include: (1) a rotation angle, (2) a first x-value indicating the left edge of the page with corrected rotation, (3) a second x-value indicating the right edge of the page with corrected rotation, (4) a first y-value indicating the top edge of the page with corrected rotation, and (5) a second y-value indication the bottom edge of the page with corrected rotation.